HPAVC/HPAVC CD-ROM.iso/VELENA17.ZIP/CONNECT4.DOC

Text File | 1997-05-28 | 30KB | 716 lines

                              -+- Velena -+-

         A Connect Four Expert System which Plays the Game Perfectly
         ===========================================================



                                 Abstract
                                 ========

Velena is a Shannon-C type strategy program written to play Connect Four.
It's based on a knowledged approach that uses eight mathematical rules to
take its decisions. Since the rules are proven to be correct, the conclusions
made by the program are also correct. In this way it has been possible to
show that Connect Four is a first player win and Velena is always able to
win when she plays first.

===============================================================================


1. Program overview
===================

    1.1. System Requirements
    ========================

    To run Velena, you will need the following system:

    * An IBM compatible, 386 or better computer (486/DX2 suggested)
    * Four megabytes of RAM.
    * A SVGA VESA-compatible graphic adapter.
    * MS-DOS 5.0 (or better) or compatible operating system.


    1.2. Freeware agreement
    =======================

    This program is to be considered freeware, which means that you can use
    and distribute it to anyone you want, provided no fee is charged except
    for media support.
    You should also not disassemble modify or reverse engineer the program
    for any reason in any circumstance.
    The program is offered as is without warrants of any kind, even if the
    best efforts have been made to produce a functional and efficient product.
    I should not be liable for any damage caused by the use or misuse of
    this program. Running the program is entirely at user's risk.

    Even if a fee is not required, I will be glad to receive a postcard from
    your hometown with your comments and suggestion about my program.


                                             The author current address is:

                                             Giuliano Bertoletti
                                             Via Bocchialini n.6
                                             Cap. 43100, Parma. Italy

                                             E-Mail:  [e-mail]
                                             Fidonet: 2:332/801.6



    1.3. Greetings
    ==============

    This program is based on the knowledged approach of L.Victor Allis
    which designed and implmented a sophisticated AI engine in a program
    called Victor.
    Velena is basically the same, except that even newer concepts and
    techinques were introduced in order to reduce the problem complexity
    (of solving the game) to a more tractable factor of magnitude.
    Moreover Velena is available to anyone, while Victor (currently) is not.
    I thank L.Victor Allis for his support while I developed Velena
    and for the theory he made for solving Connect Four.
    Without him this program wouldn't have come to light.

    I also thank Filippo Ghilardi who helped me to build the opening book
    data base which took several days of work on his Pentium 133 computer,
    and Davide Mazza who created the Velena intro logo.


    1.4. Third party material
    =========================

    Sci-Tech freeware VESA graphics library has been used to build the low
    level graphics interface.

    PMODE/W Dos Extender by Charles Scheffold and Thomas Pytel has been used
    in substitution of DOS4GW in order to create a more compact executable.

    A modified version of Gif Library by Gershon Elber (adapted to 32 bit
    compilers) has been used to handle GIF files.



2. Introduction into Connect Four
=================================

Now I'll describe the rules of the game as well as some nomenclature used
throughout this manual and some basic connect four strategy.


    2.1. Game Rules
    ===============

    Connect Four is a two players game which takes place on a 7x6
    rectangular board placed vertically between them. One player has
    21 yellow men and the other 21 red men. Each player can drop
    a man at the top of the board in one of the seven columns; the
    man falls down and fills the lower unoccupied square. Of course
    a player cannot drop a man in a certain column if it's already
    full (i.e. it already contains six men).

    Even if there's no rule about which color should play first, in order
    to avoid confusion we will assume that men are either white or black
    (instead of yellow and red) and that white, as in chess, always plays
    first.

    Note however that Velena displays men in yellow and red even if here are
    refered as white and black respectively. Therefore when playing with
    Velena, yellow always begins first.

    The object of the game is to connect four men vertically, horizzontally
    or diagonally. If the board is filled and no one has alligned four men
    then the game is drawn (that is after 42 moves if no one wins).

    Here's an example of a game won by white (O) and black (X) in fig.1 and
    fig.2 respectively. A possible draw is represented in fig.3


         .......                  .......                  OOOXOOO
         .......                  .......                  XXXOXXX
         .......                  .XO....                  OOOXOOO
         ...X...                  .XXO...                  XXXOXXX
         ...X...                  .OOX...                  OOOXOOO
         XOOOO..                  .OXOX..                  XXXOXXX

          Fig.1                    Fig.2                    Fig.3
      White (O) wins           Black (X) wins          The Game is drawn


    2.2. Nomenclature
    =================

    Since we need a way for representing a sequence of moves instead of a
    position, I will use the same nomenclature as the one used for chess.
    This means that columns are named from A to G, starting from left, and
    rows are numbered from 1 to 6 starting from the bottom.
    In this way we could represent each square of the board with a pair
    letter-number. For example the square in the middle of the lowest row
    is d1. The square above is d2 and the square on the left of d1 is c1.
    (see fig. 3)

                              6 . . . . . . .
                              5 . . . . . . .
                              4 . . . . . . .
                              3 . . . . . . .
                              2 . . . . . . .
                              1 . . . . . . .
                                A B C D E F G

                                   Fig. 3


    In this way we could write down a game as a sequence of moves.
    For example the endgame of fig.1 could have arisen from the following
    sequence of moves:

        1) d1,d2
        2) c1,d3
        3) b1,a1
        4) e1++

    where ++ indicates the player who did that move won the game (as in
    chess).


    2.3. Game Strategy
    ==================

    There are two kinds of strategies in connect four. The first consist in
    looking ahead few moves to avoid the opponent to win and in the same time
    trying to connect four men. The other is looking for a win in the long run.

    Virtually all the algorithms I have seen tend to implement the first
    strategy with some variants of alpha beta search and the most
    sophisticated ones with tree branch pruning. These strategies assure more
    or less the unvulnerability in the short run, but they are doomed to fail
    in the long run because they cannot see beyond the horizzon of few plies.

    Most of the games ends between 35th and 42nd move when you (or the
    opponent) are forced to make a particular move since there's only one
    column available. In this circumstance most of the people believe that
    the winner is lucky (if there's one). That's not it. An expert player
    is able to make this happen much time before. Actually this is what
    Velena does.

    The first step consist in noting that after white has moved, an odd number
    of free squares remains on the board. Similary after black has moved an
    even number of free square remains. When there's only one column available
    it's clear that the last square will be occupied by black (if no one wins
    first).

    Now let introduce some definitions before continuing:

    -----------------------------------------------------------------------

    ODD SQUARE: it's a square belonging to an odd row. For example d1,c1,c3,
    f5 are all odd squares.

    EVEN SQUARE: same as above except that the row is even. For example a2,
    b4,c6,e2 are all even squares.

    GROUP: it's a set of four squares connected horizzontally, vertically
    or diagonally. The first player who fills a group with his men, wins.

    THREAT: it's a group filled with three men of the same color which has
    the fourth square empty, and also the square below the empty square is
    empty.

    ODD THREAT: it's a therat in a group whose empty square is odd.

    EVEN THREAT: same as above but the empty square is even.

    DOUBLE THREAT: they are two groups which share an empty odd square;
    each group is filled with only two men (of the same color) and the
    other two squares (one for each group) are empty and are one above
    the other. The square below the shared square must be empty too.

    -----------------------------------------------------------------------

    It's then clear that if white has an odd threat and black cannot connect
    four men anywhere, the game will be eventually won by white.

    Please note that this is a sufficient condition and if black can connect
    four men somewhere, further knowledge is required.

    Similary if black has an even threat and white cannot connect four men the
    game will be eventually won by black.

    It's clear that in both cases we assume that players make the best move
    available.

    Things get more complex when both players have at least one group in
    which they can connect four men. In this case we need further
    investigation.

    If white has an odd threat and black has an even threat and the columns
    in which the threats are (i.e. the empty square) are different then
    white can still win. Of course no player must be able to connect four men
    except in the group in which he has the odd/even threat stated above.

    But if columns are the same then the lower threat (i.e. the lower
    empty square) wins.

    If both players have an odd threat the game will be drawn. Unless one
    of them can connect four men elsewhere.

    Then the strategy for white is to try to obtain an odd threat and for
    black an even threat. This is not always sufficient as the restrictions
    above shows but it's a good starting point to play connect four,
    especially when both players are humans.


    2.4. The Way Velena Plays
    =========================

    When set to her strongest level, Velena uses two different strategies
    according she's playing white or black. In both cases she uses a database
    for the opening lines. The database is made in such a way that Velena is
    always able to reach a position in which she has an odd threat when she
    plays white (and from there she's able to continue and win by herself).
    She tries to follow the longest winning line for white when she plays with
    black. The built in evaluation function which examines the positions is
    then sufficient to play the middle and end game. However, further search
    is done just to check for trivial wins few moves ahed.


    2.5. Drawbacks of the algorithm
    ===============================

    Connect Four is not complex like chess. Therefore moves tends to repeat
    many times. For example the winning line for white is very narrow, so
    narrow that the first seven moves for white are forced.
    This is the reason why Velena is forced to answer almost always in the
    same way, given the same position on the board. There are not many
    variants.

    It's not strange that a player who keeps white men and learns how to
    win a game, is then always able to win each time he plays. This because
    he can play the same game each time.

    Another drawback is that Velena pays very poor attention to distinguish
    between a win for black and a draw. They are almost the same thing for her.

    Also note that Velena does the best move (when playing with white) only
    when she starts from the empty board. If someone sets up a position and
    then tells the computer to continue the game from that point, it's not
    warranted that the computer plays at best.

    Finally the algorithm tend to resign when a game is compromised and
    doesn't fight until the end.


3. Running Velena
=================

After you have installed Velena on your hard disk, you can start the program
simply typing "connect4" at the dos prompt. As already indicated in section
1.1, the program needs among the other things a SVGA VESA compatible card.
Many cards can be made VESA compatible simply with a device driver that is
in most of the cases provided with the graphic adapter itself. If you have
any problem, look in your card manual. Besides there are also many freeware
device drivers which can make your graphic adapter become VESA compatible.

After a few seconds the computer will display the logo and then the board.
Velena is ready to play.

The program is entirely mouse driven and the commands are available as
click-able gadgets in the top of the screen.

    3.1. The Control Panel
    ======================

    As you surely already noticed, Connect Four is very simple to understand
    and doesn't require too many operations to control the game options.
    The buttons in the top of the screen can drive the program with basic
    commands. Let's see their meaning:


      - New Game

        When you want to begin a new game, click this button and then
        confirm the option by answering YES. If you make a mistake or
        you change your mind you can answer NO and the command will
        be ignored.


      - Options

        When you want to set up a match between a player and the computer
        or two players, or an autoplay, click this button.
        You can also choose the computer level this way. By default red
        side is kept by Velena and yellow side (which begins first) is kept
        by the player. The default computer level is "strong".

        If you are unable to win (which is most likely), you can lower the
        level to "normal" or "weak".


      - Hint

        If you need a hint click this button and the computer will move
        for you.


      - Take Back

        This is probably the most used option. If you make a mistake and
        you want to undo the move made, just click this button.
        Note that when a two players game is set, only the last move is
        taken back. But when you play against the computer, moves are
        taken back two at time because you can take back only after the
        computer has made it's move.
        You can also take back more than one move by clicking repeatedly
        this button.


      - About

        Shows the program current version with other informations about
        the author and greetings.


      - Quit

        When you finished to play with Velena you can click this button
        and confirm you really want to quit.


    3.2. Other commands
    ===================

    Moves are made by pointing the square in which the player in turn
    wants to play. You can also move with the keyboard by pressing keys
    1..7, where 1 is the leftmost column and 7 the rightmost.

    F1 key can be used to flip colors on the screen (although men are always
    referenced as black and white).

    A file named CONNECT4.LOG is always updated on disk each time a game is
    over and keeps track of all the games played.


    3.3. Advanced options
    =====================

    With the right mouse button you can access a pull down menu with some
    advanced features. Here a brief description of what they mean:


       - Flash last move:

       It can be use to replay the last move made. The last man flashes for
       few seconds to let you understand for example where the computer moved.


       - Show moves list:

       Shows the moves so far in the chess notation described above.
       It also shows the moves in a column-wise manner which denotes only
       the column in which a player moved.


       - Position analysis

       Analyzes the current position on the board (for the side which is NOT
       in turn to move) and tells which is the theorical result that can be
       achieved if that player plays at best. Please note that only sufficient
       conditions are used for the analysis. This means that if the computer
       tells a game can be won, this is true, but if the computer says nothing
       this doesn't mean that a game can't be won. In other words it proceeds
       by sufficient conditions, not necessary.


       - Oracle analysis

       This is probably the most difficult feature to explain. It gives a
       detailed report of the oracle status (which is one of the three engines
       which drive Velena, and besides the most important one).
       Since rules definitions and applications are difficult to understand,
       I suggest you to refer to L.V.Allis thesis "A knowledge based approach
       of Connect Four" to know more. Once you red and understood that thesis
       you'll be able to understand the report Velena gives with this option.
       Refer to paragraph 4.8 for further informations.
       Please note that also the oracle proceeds by sufficient conditions;
       there are some positions where the game result is clear and the oracle
       seems not to foresee it.


       - Reset counters

       Resets the two counters which keep players score (shown at the top
       of the board).


       - Change colors

       It simply changes the palette, swapping the three main colors
       components. This leads to a total of six different combinations.


       - Repaint Desktop

       It's useful when you run Velena on a multitasking operating system
       and you switch back and forth from task to task. Since the display
       may become corrupted, using this option should solve the problem.


       - Save moves list

       Writes to disk an ascii file with the moves made. The file name is
       choosen automatically.


       - Save screen to disk

       Writes an image in GIF format with the current position on the board.
       The GIF can be in two colors or in 256 colors according to your needs.
       The 256 color GIF is the current Velena screen, while the 2 colors
       screen is simply a diagram which is pretty useful if you want to print
       it.



4. Why Velena is so special
===========================

As already said before, Velena is an expert system able to play the game
perfectly. This means that if the program is set to it's maximum level of
strength she always wins when she plays first and she is almost impossible
to beat when she plays second (until you make a few games and you will
learn how to beat her by the program herself).

Of course if you are a beginner you can set a lower difficulty level for the
computer. This is useful if you are interested in learning how to play.


    4.1. Game complexity
    ====================

    Although at first sight Connect Four doesn't seem a very complex game
    in terms of combinations of moves and the number of reachable different
    positions on the board, it should be noticed that it's not a so trivial
    game as it looks. Let's see some mathematics behind it.

    First we can make a raw estimation of game complexity noting that since
    each square can be empty or occupied by either white or black, each
    square can be in only three different states, leading a total game
    complexity of 3^42 which is in the order of 10^20. Of course this is an
    upper bound which takes in count also the illegal positions.

    It is possible to make some finer estimations that reduces the number of
    legal positions, anyway even the finest estimation gives us an order
    of magnitude of 7.1 x 10^13, which is still to high for a complete
    enumeration. To build up a brute force attack several terabytes of disk
    space would be required, and current technology is far away from this
    possibility. Besides the space requirements, also the time requirements
    would be out of what are called "reasonable resources". Finally it would
    be almost impossible to distribute the program.


    4.2. So Velena is not a brute force attack against Connect Four?
    ================================================================

    Definitly not. Velena is an intelligent program which is able to
    predict the final result of a game using complex mathematics, and
    efficient search strategies. The program is compact and strong;
    only a tiny opening book of about 60.000 positions is used for the
    opening lines. All the rest is calculated on fly.


    4.3. So why should I use Velena if it's unbeatible?
    ===================================================

    Well, there are several reasons why this program can be useful.
    First it represents the final word on Connect 4 (or so I hope):
    no program or living man can outperform Velena.

    Besides, Velena is very useful to train yourself against a human
    player. If you want to become a strong player then you should train
    yourself with a strong player. And Velena is the strongest.


    4.4. But is Velena really so perfect?
    =====================================

    Well, it's perfect in the sense that she's always able to win if she
    plays first. This because it can be mathematically shown that Connect
    Four can be won by the player which plays first (if it plays well) no
    matter how good the opponent is.

    Of course if Velena plays second, there's still a chance for the human
    player to defeat her. Once you learned how, you can easiliy win.
    More over the purpose of the computer in this case (when playing second)
    is not to win, but to avoid losing, if possible. In other words Velena
    considers a draw a good result if it plays with red men.


    4.5. So Velena destroyed Connect Four?
    ======================================

    Yes, but humans are humans and machines are machines. Connect Four is
    still interesting if played between two men. Of course there are no
    chances between a man and a computer, like there are no chances between
    a man and a car. The latter will run always faster.


    4.6. Why does Velena play almost always the same game when she's
    in autoplay?
    =================================================================

    Connect four is not like chess. Even if the game is not as trivial
    as tic tac toe, the complexity is much smaller than chess. This of
    course leads to a limited number of variants and often the moves are
    forced. For example there's only one winning way for white and the
    first seven moves are forced for him. If he choses another move, black
    can draw. Similary black has only one strong defensive line (which of
    course fails in the long run) which can protect him from a premature
    loss. It's clear that once you learn how to infiltrate in this line,
    you are likely to win each time against black.


    4.7. Isn't Velena too slow in replying?
    =======================================

    It depends on which machine she runs. Theorically it can run on a 386
    based processor, but she surely will take a lot of time. At least a
    486DX2 is required to play at decent speed.
    Anyway the algorithm behind is very complex, and no time is wasted in
    useless delays. Velena needs all the resources she uses. Believe me!


    4.8. Where can I find the complete description of the algorithms used here?
    ===========================================================================

    You can try:

    ftp://ftp.cs.vu.nl/~victor/connect4.zip
    ftp://ftp.cs.vu.nl/~victor/thesis.zip

    this is the documentation made available by L.Victor Allis and surely
    it's very interesting. Of course I am not sure that it will be there
    forever. Please contact [e-mail] for more informations.

    Keep also in mind that this program is based on his theory but it does
    not follow it completely. For example the mathematical rules have been
    reduced from nine to eight.

    You can also refer to Velena Home Page at:
    http://www.ce.unipr.it/~gbe/velena.html


    4.9. Where can I get the last version of Velena
    ===============================================

    Check out Velena's Home Page at:

    http://www.ce.unipr.it/~gbe/velena.html
    or use a net serach engine.


    4.10. Is the source code of Velena available to the public?
    ===========================================================

    No, at the moment it's not. Maybe one day it will.


    4.11. Who's F.Alinovi and why did he say: "...who wants to make four?"
    ======================================================================

    He's a friend. After I bored him telling the inner workings of
    Velena and the clever idea behind the algorithm he answered that way.
    He also added that I was losing my time. Poor little fellow! :))))


    4.12. What's "a Shannon-C type program" mean?
    =============================================

    In his famous paper in 1950 C.Shannon describes three methods by which
    a machine could play a strategy game (such chess, checkers, connect four
    and so on...). The C-type method consist in emulating human mind to take
    decisions. In other words the eight mathematical rules Velena uses are
    not based on a search algorithm but on the properties of the game.
    The A-type method instead is based on pure brute force search.
    Just to be fair Velena is not only a Shannon-C type program since it
    also uses some search algoritms to play, anyway the great difference in
    playing capabilities relies just on this knowledged approach, which made
    possible to solve the game.


    4.13 Why you don't want any money for your program?
    ===================================================

    Because in this way each one has the possibility to use this program.
    If I ask for a registration, the program won't spread around very much
    and besides I won't become rich. :-)))


    4.14 Why isn't there the possibility to change the board size?
    ==============================================================

    I think the standard 7x6 board is enough. Other sizes are not very
    interesting. For example it can easily be shown that black can draw
    on any (2n)x6 board. Here's the 6x6 board algorithm black can use to
    draw any game.

    step 1: if white plays column A,B,E or F, you play follow up (the same
            column).

    step 2: when white plays column C or D for the first time you answer
            in the other column.

    step 3: if white plays column C or D again you answer in the same column
            until the column is full. If you cannot answer that way because
            the column is full, then you play the other column.

    If black follows these three steps, the game can be drawn, no matter what
    white does.


    4.15 Which language have you used to write Velena?
    ==================================================

    Velena is essentialy written in C and compiled using the Watcom C/C++ V10.0
    The AI engine is completly portable to other 32 bit systems, however a
    small part of the remaining code is written in 80386 assembly in order
    to speed up the graphics.


    4.16 How long did it take to write Velena?
    ==========================================

    I started the whole work only with the theory of L.V.Allis in my hands and
    not a line of code. It took almost ten months of which half were spent in
    calculations to build the opening book data base. One in understanding the
    theory, and the rest in refining the algorithm and designing the graphics.
    The work proceeded on two computers; I used one to develop the program
    and the other to build the database.


    4.17 Why did you call her Velena?
    =================================

    I don't know, I simply liked the name. However it's very similar to
    "Veleno" which in italian means "poison". The intro logo recall this
    sensation too. I have nothing else to say about it. :-(((



===============================================================================

    Further details will be given if requested. Please write in english or
    in italian.

===============================================================================

                                                     The author:
                                                     Giuliano Bertoletti
                                                     Via Bocchialini n.6
                                                     Cap. 43100 Parma
                                                     [e-mail]